package uk.ac.strath.cis.metric_spaces.indices;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import uk.ac.strath.cis.metric_spaces.framework.AbstractMetricIndex;
import uk.ac.strath.cis.metric_spaces.framework.Distance;
import uk.ac.strath.cis.metric_spaces.framework.MetricIndex;

/**
 * @author Robert
 *
 * @param <E>
 */
public class SpatialApproximationTree<E> extends AbstractMetricIndex<E> {
    /**
     * @author Robert
     *
     * @param <T>
     */
    static class Pair<T> {
        T first;
        T second;

        public Pair(T first, T second) {
            this.first = first;
            this.second = second;
        }

        @SuppressWarnings("unchecked")
        @Override
        public boolean equals(Object other) {
            if (other == null)
                return false;
            try {
                Pair<T> that = (Pair<T>) other;
                return (this.first.equals(that.first) && this.second
                        .equals(that.second))
                        || (this.first.equals(that.second) && this.second
                                .equals(that.first));
            } catch (ClassCastException e) {
                return false;
            }
        }

        @Override
        public int hashCode() {
            return (first.hashCode() + second.hashCode());
        }
    }

    static final Map<Pair<?>, Double> cache = new HashMap<Pair<?>, Double>();
    private E root;
    private List<SpatialApproximationTree<E>> children = new ArrayList<SpatialApproximationTree<E>>();
    private double range;

    /**
     * @param metric
     */
    public SpatialApproximationTree(Distance<E> metric) {
        super(metric);
    }

    /**
     * @param copy
     */
    public SpatialApproximationTree(SpatialApproximationTree<E> copy) {
        super(copy);
    }

    /* (non-Javadoc)
     * @see uk.ac.strath.cis.rmoss.metric_spaces.framework.AbstractMetricIndex#insert(java.util.Set)
     */
    public void insert(Set<E> elements) {
        super.insert(elements);
        insert(new ArrayList<E>(elements));
    }

    /**
     * @param elements
     */
    public void insert(List<E> elements) {
        root = elements.get(0);
        buildTree(root, elements.subList(1, elements.size()));
    }

    private void buildTree(E pivot, List<E> set) {
        Map<E, List<E>> neighbours = buildNeighbours(pivot, set);
        List<E> nonNeighbours = getNonNeighbours(set, neighbours.keySet());
        addNonNeighboursAsChildren(neighbours, nonNeighbours);
    }

    private void addNonNeighboursAsChildren(Map<E, List<E>> neighbours,
            List<E> nonNeighbours) {
        for (E e : nonNeighbours) {
            // find which neighbour to put it in
            E tempN = null;
            double tempD = Double.MAX_VALUE;
            for (E n : neighbours.keySet()) {
                double d2 = distanceFromCache(e, n);
                if (d2 < tempD) {
                    tempN = n;
                    tempD = d2;
                }
            }
            neighbours.get(tempN).add(e);
        }

        for (int i = 0; i < children.size(); i++) {
            SpatialApproximationTree<E> child = children.get(i);
            List<E> bag = neighbours.get(child.root);
            child.buildTree(child.root, bag);
        }

    }

    private List<E> getNonNeighbours(List<E> set, Collection<E> neighbours) {
        List<E> l = new ArrayList<E>();
        for (E e : set) {
            if (!neighbours.contains(e)) {
                l.add(e);
            }
        }
        return l;
    }

    private double distanceFromCache(E first, E second) {
        Pair<E> pair = new Pair<E>(first, second);
        if (cache.containsKey(pair)) {
            return cache.get(pair);

        } else {
            double d = distance(first, second);
            cache.put(pair, d);
            return d;
        }
    }

    private Map<E, List<E>> buildNeighbours(final E pivot, List<E> set) {
        Map<E, List<E>> neighbours = new HashMap<E, List<E>>();
        range = 0.0;

        Collections.sort(set, new Comparator<E>() {

            public int compare(E first, E second) {
                double d1 = distance(first, pivot);
                cache.put(new Pair<E>(first, pivot), d1);
                double d2 = distance(second, pivot);
                cache.put(new Pair<E>(second, pivot), d2);
                return d1 < d2 ? -1 : d1 == d2 ? 0 : 1;
            }
        });
        for (E v : set) {
            double r = distanceFromCache(v, pivot);
            range = Math.max(range, r);
            boolean closerToNeighbour = false;
            for (E b : neighbours.keySet()) {
                if (distanceFromCache(v, b) < r) {
                    closerToNeighbour = true;
                }
            }
            if (!closerToNeighbour) {
                neighbours.put(v, new ArrayList<E>());
                SpatialApproximationTree<E> tree = new SpatialApproximationTree<E>(
                        this);
                tree.root = v;
                children.add(tree);
            }
        }
        return neighbours;
    }

    /* (non-Javadoc)
     * @see uk.ac.strath.cis.rmoss.metric_spaces.framework.MetricIndex#rangeQuery(java.lang.Object, double)
     */
    public Set<E> rangeQuery(E element, double radius) {
        HashSet<E> returnSet = new HashSet<E>();
        rangeSearch(this, element, radius, distanceFromCache(root, element),
                returnSet);
        return returnSet;
    }

    private void rangeSearch(SpatialApproximationTree<E> a, E q, double r,
            double mind, Set<E> returnSet) {
        double dist_a_q = distanceFromCache(a.root, q);
        if (dist_a_q <= a.range + r) {
            if (dist_a_q <= r) {
                returnSet.add(a.root);
            }
            mind = min(q, mind, a.children);
            for (SpatialApproximationTree<E> b : a.children) {
                if (distanceFromCache(b.root, q) <= mind + 2 * r) {
                    rangeSearch(b, q, r, mind, returnSet);
                }
            }
        }
    }

    private double min(E q, double mind,
            List<SpatialApproximationTree<E>> children) {
        double min = mind;
        for (SpatialApproximationTree<E> child : children) {

            double distance = distanceFromCache(q, child.root);
            min = Math.min(min, distance);

        }
        return min;
    }

    private String toString(StringBuilder sb, SpatialApproximationTree<E> node) {
        if (node == null) {
            return "";
        }
        sb.append(node.root + "[" + node.range + "]");
        if (!node.children.isEmpty()) {
            sb.append("(");
            int i = 0;
            for (SpatialApproximationTree<E> child : node.children) {
                toString(sb, child);
                if (i < node.children.size() - 1) {
                    sb.append(",");
                }
                i++;
            }
            sb.append(")");
        }
        return sb.toString();
    }

    /* (non-Javadoc)
     * @see java.lang.Object#toString()
     */
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        return this.toString(sb, this);
    }
    
    @Override
    public MetricIndex<E> clone() {
    	return new SpatialApproximationTree<E>(this);
    }

}
